import java.io.IOException;

//  On my honor:
//	
//  - I have not used source code obtained from another student, 
//    or any other unauthorized source, either modified or unmodified.  
//	
//  - All source code and documentation used in my program 
//    is either my original work, or was derived by me from the source
//    code published in the textbook for this course.
//	
//  - I have not discussed coding details about this project with anyone
//    other than my instructor, ACM/UPE tutors or the GTAs assigned to this
//    course. I understand that I may discuss the concepts of this program
//    with other students, and that another student may help me debug my
//    program so long as neither of us writes anything during the discussion
//    or modifies any computer file during the discussion.  I have violated
//    neither the spirit nor letter of this restriction.
//	

/**
 * @author Christopher Suh, Eric Yoo
 * 
 *         TODO: modify to hold a reference to a BufferPool which interacts with
 *         the output file
 * 
 *         TODO: combine this MemManager from Project 1 with MemManager from
 *         Project 2 to ensure our needed functionality works.
 * 
 *         TODO: fix comparator to fit into handle structure
 * 
 *         TODO: Make this a variable-length memory manager
 */
public class MemManager {
	private LinkedList freeBlockList;
	private int block_size;
	private int cur_size;
	private BufferPool buffer_;

	/**
	 * Constructor
	 * 
	 * @param poolsize
	 *            size of the byte array to allocate
	 */
	MemManager(int block_size, BufferPool pool) {
		freeBlockList = new LinkedList();
		freeBlockList.insert(0, 0);
		this.block_size = block_size;
		buffer_ = pool;
		cur_size = 0;
	}

	/**
	 * Allocates a block of memory of a given size and returns the address.
	 * 
	 * @param size
	 *            size of the memory block requested
	 * @return handle that contains the address of the first byte of the block
	 */
	public Integer allocate(int size) {
		int index = 0;
		size++;
		Integer handle;

		// check size for valid number,

		// find memory block in pool for space using best fit rule
		freeBlockList.resetCurNode();
		ListNode cur = freeBlockList.getNext(), bestFit = null;
		while (cur != null) {
			if (cur.getSize() >= size) {
				bestFit = freeBlockList.removeNode(cur);
				index = bestFit.getIndex();
				break;
			}
			cur = freeBlockList.getNext();
		}

		while (bestFit == null) {
			addBlock();
			freeBlockList.resetCurNode();
			cur = freeBlockList.getNext();
			while (cur != null) {
				if (cur.getSize() >= size) {
					bestFit = freeBlockList.removeNode(cur);
					index = bestFit.getIndex();
					break;
				}
				cur = freeBlockList.getNext();
			}
		}
		handle = index;

		// if the best fit free block is larger than needed, insert a
		// free block into the list of according index and size.
		if (bestFit.getSize() > size) {
			freeBlockList.insert(index + size, bestFit.getSize() - size);
		}

		// Return the newly created handle corresponding to the inserted data.
		// If there is not enough room to hold the new data, a null value will
		// be returned.
		return handle;
	}

	/**
	 * Deallocates the given block from memory and frees that block.
	 * 
	 * @param addr
	 *            address of the first byte in of the block.
	 */
	public void deallocate(Integer addr) {
		int index = addr;
		byte[] buff = new byte[256];
		int size = 0;
		try {
			size = buffer_.read(addr, buff) + 1;
		} catch (IOException e) {
			e.printStackTrace();
		}

		// Traverse through the freelist and search for adjacent blocks.
		freeBlockList.resetCurNode();
		ListNode cur = freeBlockList.getNext();
		ListNode before = null, after = null;
		while (cur != null) {
			if(cur.getIndex() == index)
				return;
			if (cur.getIndex() + cur.getSize() == index) {
				before = cur;
			}
			if (index + size == cur.getIndex()) {
				after = cur;
			}

			cur = freeBlockList.getNext();
		}

		// If there is are any free blocks adjacent to the newly created free
		// block, merge them and insert the new free block.
		if (before != null) {
			before = freeBlockList.removeNode(before);
			index = before.getIndex();
			size = size + before.getSize();
		}
		if (after != null) {
			after = freeBlockList.removeNode(after);
			size = size + after.getSize();
		}
		freeBlockList.insert(index, size);
	}

	/**
	 * internal method used when the memory pool needs to be expanded
	 */
	private void addBlock() {
		freeBlockList.resetCurNode();
		ListNode cur = freeBlockList.getNext();
		while (cur != null) {
			if (cur.getIndex() + cur.getSize() == cur_size) {
				cur = freeBlockList.removeNode(cur);
				freeBlockList
						.insert(cur.getIndex(), cur.getSize() + block_size);
				cur_size += block_size;
				return;
			}
			cur = freeBlockList.getNext();
		}
		freeBlockList.insert(cur_size, block_size);
		cur_size += block_size;
	}
	public void dump() {
		freeBlockList.resetCurNode();
		ListNode cur = freeBlockList.getNext();

		// If freelist is not empty, print out the free blocks.
		if (cur != null) {
			System.out.println("Freelist: [" + cur.getIndex() + ", "
					+ (cur.getIndex() + cur.getSize() - 1) + "] ("
					+ cur.getSize() + " bytes);");

			// Traverse through the freelist and print out the free blocks.
			while (true) {
				cur = freeBlockList.getNext();
				if (cur != null) {
					System.out.println("          [" + cur.getIndex() + ", "
							+ (cur.getIndex() + cur.getSize() - 1) + "] ("
							+ cur.getSize() + " bytes);");
				} else {
					break;
				}
			}
		}
		else
		{
			System.out.println("FreeBlockList is empty.");
		}
		System.out.println();
	}

	public void clear() {
		freeBlockList = new LinkedList();
		freeBlockList.insert(0, 0);
		cur_size = 0;
	}
}
